How does a Priority Queue handle ties in priority? (Stability)

Priority Queue Stability

javascript

1
A plain heap generally guarantees priority ordering, not FIFO ordering among equal priorities.
2
A monotonically increasing sequence number provides deterministic FIFO tie-breaking.
3
The comparison should first use priority and then sequence number.
4
Stable behavior is important in schedulers, event processing, and fair task execution.
5
Tie-breaking rules should be explicitly documented because unspecified ordering can create nondeterministic application behavior.

Difficulty: 5/10

Topics: stability, heap implementation, ordering guarantees

0-2 years experience

1
You have a min‑heap priority queue and you insert task A then task B, both with priority 5. Which task will be dequeued first and why?
2
Implement a simple priority queue for a scheduler where tasks with the same priority must run in FIFO order. What change would you make to a binary heap to achieve that?
3
If you use the language's built‑in priority queue that doesn't document stability, what could happen when you push several items with identical priority?

2-5 years experience

1
Your team's job queue started processing same‑priority jobs out of submission order. Walk me through how you'd debug and fix the issue.
2
We need O(log n) inserts but also FIFO for ties. Discuss two design options and their trade‑offs.
3
During a load test, high‑priority jobs are delayed because many low‑priority jobs with identical priority are being processed out of order. How would you adjust the priority queue implementation?

5-8 years experience

1
Design a distributed task scheduler that uses a priority queue across multiple nodes. How do you ensure consistent tie‑breaking across the cluster?
2
Our real‑time messaging system shows out‑of‑order delivery for messages with the same priority at peak load. What architectural changes would you propose to guarantee stable ordering while keeping latency low?
3
Explain the performance and memory impact of adding a timestamp tie‑breaker to each element in a heap that stores billions of items.

8+ years experience

1
We are migrating a legacy C++ priority queue that lacks stability to a new Go service. How would you plan the migration to avoid breaking clients that rely on FIFO ordering for equal priorities?
2
Several microservices have implemented their own priority queues with different tie‑breaking rules. Propose a company‑wide strategy to standardize stability guarantees and reduce technical debt.
3
In a multi‑tenant platform, all tenants share a global priority queue. How would you design the tie‑breaking mechanism to ensure fairness, isolation, and support tenant‑specific ordering policies?